Data Flow Analysis
开局一张图
如图所示一共有三种数据流分析应用分别为reaching definitions、live variables、available expressions、available expressions，不同的数据流分析有不同的 data abstraction和不同的 flow safe-approximation strategies，如不同的 transfer functions 和 control-flow handlings
Overview of Data Flow Analysis
Data Flow Analysis可以概括为：How Data Flows on CFG，展开来的英文就是 How application-specific Data Flows through the Nodes(BBs/statements) and Edges(control flows) of CFG(a program)？
How application-specific Data :对数据的抽象(data abstraction) e.g:+, -, 0 等
Flows ：根据分析的类型，做出合适的估算
Nodes：数据如何通过转换函数（Transfer functions）进行分析处理
Edges ：Control-flow如何处理，例如两个控制流汇入一个BB
Notations for Transfer Function’s Constraints
转换函数的约束规则的基本概念，主要分为这两种analysis
Notations for Control Flow’s Constraints
控制流约束规则如下
Reaching Definitions Analysis
A definition d at program point p reaches a point q
if there is a path from p to q such that d is not “killed” along that path
假定 x 有定值 d (definition)，如果存在一个路径，从紧随 d 的点到达某点 p，并且此路径上面没有 x 的其他定值点，则称 x 的定值 d 可达 (reaching) p。如果在这条路径上有对 x 新的定值，我们说变量 x 的这个定值 d 被杀死 (killed) ，其实就是说给变量v一个定义d，存在一条路径使得程序点p能够到达q，且在这个过程中不能改变v的赋值
应用于检测可能未初始化的变量；例如，在CFG的Entry节点，为所有的变量引入dummy definition（也就是代表未初始化变量的定义），如果dummy定义可到达点p，且定义对应的变量被使用，则这个点可能存在undefined错误；
Data Flow Values/Facts
算法如图：
Transfer Function:
OUT[B]=genB∪(IN[B]−killB) gen 的是新的、definitionkill 的是其他 Basic Block 里定义 v 的 definitions（如对于一条赋值语句 D: v = x op y，该语句生成了 v 的一个定值 D，并杀死程序中其它对变量 v 定义的定值）
Control Flow:
IN[B]=∪P a predecessor of B OUT[P]
一个例子如下：
一个例子运行结果为
Live Variables Analysis
Live variables analysis tells whether the value of variable v at program point p could be used along some path in CFG starting at p. If so, v is live at p; otherwise, v is dead at p.
某程序点p处的变量v，从p开始到exit块的CFG中是否有某条路径用到了v，如果用到了v，则v在p点为live，否则为dead。其中有一个隐含条件，在点p和引用点之间不能重定义(redefined)v。
可以应用于寄存器分配，当一个变量不会再被使用，那么此变量就可以从寄存器中腾空，用于新值的存储。
Data Flow Values/Facts
Control Flow：
OUT[B]=∪S a successor of BIN[S]
Transfer Function:
IN[B]=useB∪(OUT[B]−defB) use 是指那些被用到，且用之前在本 basic block 没有被重定义过的变量、def 是指在本 basic block 中重定义的变量
算法如下：
例子如下：
一个例子运行结果为
Available Expressions Analysis
An expression x op y is available at program point p if all paths from the entry to p must pass through the evaluation of x op y, and after the last evaluation of x op y, there is no redefinition of x or y
程序点p处的表达式x op y可用需满足2个条件，一是从 entry 到 p 点必须经过x op y，二是最后一次使用 x op y 之后，没有重定义操作数 x、y。（如果重定义了 x 或 y，如 x = a op2 b，则原来的表达式 x op y 中的x或y就会被替代）
Transfer Function：
OUT[B]=genB∪(IN[B]−killB) gen：基本块求值 x op y，且之后没有对 x 或 y 赋值、kill：基本块对 x 或 y 赋值，且没有重新计算 x op y（如果重新计算，即使值不一样，也属于 gen)
Control Flow:
IN[B]=∩P a predecessor of BOUT[P]
算法如下：
运行实例如下：
